1. Field of the Invention
The present invention relates generally to the field of imaging processing, and more particularly to rendering color images.
2. Background of the Invention
Display devices, such as printers, cathode ray tubes (CRT), plasma screens, liquid-crystal displays (LCD), and the like render images using small spots, referred to as “picture elements” or “pixels.” At times, an image with a broader range of colors than the device's limited number of basic colors may need to be rendered by the device. Increased color depth may be obtained at the expense of spatial resolution by adding colored noise to the displayed pixels and relying on the human visual system to filter out the noise and perceive a wider range of colors.
One method for creating the appearance of new colors and shades is called “dithering.” Although a number of dithering methods exist, dithering generally involves comparing image pixels values with respective threshold values of a dithering matrix. A dithering matrix, which consists of an array of threshold values, is conceptually overlaid onto the image pixel array. Each of the image pixels is processed by comparing its tonal value to the associated dither matrix value. The output value, i.e., the rendered image or display pixel value, is generated based on the comparison. For example, if the display supports only binary output, the input image pixels may be mapped to output pixels as follows. If the image value equals or exceeds the dither matrix threshold value, the output pixel is illuminated or receives an ink dot (depending on whether the display device is a screen or a printer). Otherwise, it is not illuminated or does not receive an ink dot. Note that if the dither matrix is smaller than the image array, the dither array is tiled (i.e., repeated side-by-side) over the image array in order to cover the entire image array. The described binary dither can be extended to multi-level dither schemes for devices that support multiple output levels at each pixel location.
Although dithering can be an effective method for trading off spatial resolution to improve perceived color depth, there are limits to its use. For example, multi-level dithering for low and medium resolution devices poses problems since the dither noise may easily become unacceptably visible due to insufficient spatial resolution. Furthermore, a direct extension of monochrome multi-level dither techniques to multiple color channels can result in higher noise and visual artifacts arising from dithering between too many palette colors to render a target color and from interference effects between the different or same dither matrices used to dither the different color channels.
Because most color dithering techniques involve dithering each device color coordinate independently, if a display device has n device color coordinates (e.g., for a Red-Green-Blue (RGB) display, n=3, for a Cyan-Magenta-Yellow-Black (CMYK) display, n=4), dithering each device color coordinate independently, by direct extension of monochrome dithering methods, results in using linear combinations of up to 2n palette colors. And, these colors are constrained to be the outer product of the colors along each device color axis, which results in much reduced freedom for choosing the colors that comprise the palette. While increasing the number of colors in a palette reduces dither noise, dithering between a large number of colors from a small color palette, particularly in a low or medium resolution device, typically results in increased perceived noise in the dithered image. Furthermore, since there is limited freedom in choosing the colors that form the palette (since each channel is independently dithered), perpetually significant regions, such as, for example, face tones, cannot be given more bits for smoother representation without significantly sacrificing color quality in other regions of the color gamut.
Accordingly, what is needed are low-noise dithering methods, particularly low-noise dithering methods for use with displays with spatial resolution limits or with color palettes that contain a number of pre-allocated colors.